//Given the root of a binary tree, determine if it is a valid binary search tree
// (BST).
//
// A valid BST is defined as follows:
//
//
// The left subtree of a node contains only nodes with keys less than the node's
// key.
// The right subtree of a node contains only nodes with keys greater than the no
//de's key.
// Both the left and right subtrees must also be binary search trees.
//
//
//
// Example 1:
//
//
//Input: root = [2,1,3]
//Output: true
//
//
// Example 2:
//
//
//Input: root = [5,1,4,null,null,3,6]
//Output: false
//Explanation: The root node's value is 5 but its right child's value is 4.
//
//
//
// Constraints:
//
//
// The number of nodes in the tree is in the range [1, 104].
// -231 <= Node.val <= 231 - 1
//
// Related Topics 树 深度优先搜索 递归
// 👍 1085 👎 0


package leetcode.editor.cn;

//Java：Validate Binary Search Tree
class P98ValidateBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P98ValidateBinarySearchTree().new Solution();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        System.out.println(solution.isValidBSTDfs(root));
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {



        public boolean isValidBSTV(TreeNode root) {
           return isValidBSTPre(root);
        }

        TreeNode prev;
        public boolean isValidBSTPre(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (!isValidBSTPre(root.left)) {// 递归左子树是否是二叉搜索树
                return false;
            }

            // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
            if (prev != null && prev.val >= root.val){
                return false;
            }
            prev = root;
            // 递归右子树是否是二叉搜索树
            return isValidBSTPre(root.right);
        }

        public boolean isValidBSTDfs(TreeNode root) {

            return isValidBST(root, null, null);

        }

        public boolean isValidBST(TreeNode root, TreeNode minNode, TreeNode maxNode) {
            if (root == null) {
                return true;
            }
            if (minNode != null && minNode.val >= root.val) {
                return false;
            }
            if (maxNode != null && maxNode.val <= root.val) {
                return false;
            }
            return isValidBST(root.left, minNode, root) && isValidBST(root.right, root, maxNode);
        }

        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            TreeNode max = getMin(root.right);
            TreeNode min = getMax(root.left);
            if (min != null && min != root && min.val >= root.val) {
                return false;
            }
            if (max != null && max != root && max.val <= root.val) {
                return false;
            }
            return isValidBST(root.left) && isValidBST(root.right);

        }

        public TreeNode getMin(TreeNode treeNode) {
            if (treeNode == null) {
                return null;
            }
            if (treeNode.left == null) {
                return treeNode;
            }
            return getMin(treeNode.left);
        }

        public TreeNode getMax(TreeNode treeNode) {
            if (treeNode == null) {
                return null;
            }
            if (treeNode.right == null) {
                return treeNode;
            }
            return getMax(treeNode.right);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
